package offer

import "sort"

/*
时间复杂度:O(N^2)
空间复杂度:O(1)

数组中3数之和为0的系列问题
https://leetcode-cn.com/problems/1fGaJU/solution/shua-chuan-jian-zhi-offer-day05-shu-zu-i-e2af/

一、先排序，然后才能使用三指针(最外层循环固定一个指针，然后对剩下的元素进行双指针)
三指针,最外层循环固定一个指针k for k := 0; k < n-2; k++
然后用i := k+1, j=n-1, 通过双指针找到-nums[k]的值, 则nums[k]+nums[i]+nums[j]==0

注意,如何跳过前后元素重复的情况:
1.针对k, 当 k > 0 && nums[k]== nums[k-1] {continue}
2.针对i,j
for i < j && nums[i] == nums[i-1] {
	i++
}

for i < j && nums[j] == nums[j+1] {
	j--
}
*/

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	ans := make([][]int, 0)
	n := len(nums)
	for k := 0; k < n-2; k++ {
		if k > 0 && nums[k] == nums[k-1] {
			continue
		}
		i, j := k+1, n-1
		target := -nums[k]
		for i < j {
			sum := nums[i] + nums[j]
			if sum == target {
				ans = append(ans, []int{nums[k], nums[i], nums[j]})
				// 这一步可以保证下面解决重复情况时,nums[i-1]和right[j+1]不会越界
				i++
				j--
				// 解决重复的情况
				for i < j && nums[i] == nums[i-1] {
					i++
				}
				for i < j && nums[j] == nums[j+1] {
					j--
				}
			} else if sum > target {
				j--
			} else {
				i++
			}
		}
	}
	return ans
}
